/*-------------------------------------------------------------------------
 *
 * hashfn.c
 *		通用哈希函数，以及用于 dynahash.c 的哈希函数
 *		哈希表
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/common/hashfn.c
 *
 * NOTES
 *	  预计哈希函数的 32 位结果的每一位都是
 *	  像其他位一样随机；未能确保这一点可能会导致哈希表性能不佳。
 *	  在大多数情况下，哈希函数应使用 hash_bytes() 或其变体 hash_bytes_uint32()，
 *	  或 wrappers hash_any() 和 hash_uint32，定义在 hashfn.h 中。
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "common/hashfn.h"
#include "port/pg_bitutils.h"


/*
 * 这个哈希函数由 Bob Jenkins 编写
 * (bob_jenkins@burtleburtle.net)，并由 Neil Conway 表面上适配
 * 给 PostgreSQL。有关这个哈希函数的更多信息，请查看 http://burtleburtle.net/bob/hash/doobs.html，
 * 或者 Bob 在 Dr. Dobb's Journal 1997 年 9 月的文章。
 *
 * 在当前的代码中，我们采用了 Bob 2006 年更新的哈希
 * 函数，以在适当对齐时按字获取数据。
 * 这带来了有用的加速，但代价是必须维护
 * 四条代码路径（对齐与未对齐，以及小端与大端）。
 * 它还使用了两个独立的混合函数 mix() 和 final()，而不是
 * 一个较慢的多用途函数。
 */

/* 获取在非 uint32 对齐地址中设置的位的位掩码 */
#define UINT32_ALIGN_MASK (sizeof(uint32) - 1)

#define rot(x,k) pg_rotate_left32(x, k)

/*----------
 * mix -- 可逆地混合 3 个 32 位值。
 *
 * 这是可逆的，因此在 mix() 之前 (a,b,c) 中的任何信息
 * 在 mix() 之后仍然在 (a,b,c) 中。
 *
 * 如果四对 (a,b,c) 输入通过 mix()，或通过
 * mix() 以反向方式运行，则输出中至少有 32 位在
 * 一对中有时是相同的而在另一对中不同。
 * 这是通过以下方式进行测试的：
 * * 差异为一个比特、两个比特的对，任何组合
 *	 的 (a,b,c) 的高位，或任何组合的
 *	 (a,b,c) 的低位。
 * * “差异”被定义为 +, -, ^, 或 ~^。对于 + 和 -，我将
 *	 输出增量转换为格雷码 (a^(a>>1))，因此一串 1（如
 *	 通过减法通常产生的）看起来像是一个 1 比特
 *	 的差异。
 * * 基值是伪随机的，都是零但有一个比特被设置，或
 *	 所有零加上一个从零开始的计数器。
 *
 * 这并没有实现雪崩。 (a,b,c) 的输入比特有些未能影响
 * (a,b,c) 的一些输出比特，尤其是 a。最彻底混合的值是 c，
 * 但它实际上甚至没有在 c 中实现雪崩。
 *
 * 这允许一些并行性。 读取后写入在影响比特数量上有效，
 * 所以混合的目标与并行性的目标相反。我尽了所能。旋转
 * 在我能接触到的每台机器上似乎与移位的成本一样高，
 * 而旋转对高位和低位更友好，因此我用了旋转。
 *----------
 */
#define mix(a,b,c) \
{ \
  a -= c;  a ^= rot(c, 4);	c += b; \
  b -= a;  b ^= rot(a, 6);	a += c; \
  c -= b;  c ^= rot(b, 8);	b += a; \
  a -= c;  a ^= rot(c,16);	c += b; \
  b -= a;  b ^= rot(a,19);	a += c; \
  c -= b;  c ^= rot(b, 4);	b += a; \
}

/*----------
 * final -- 将3个32位值(a,b,c)最终混合成c
 *
 * 仅在几个比特位上有所不同的(a,b,c)值通常会产生看起来完全不同的c值。
 * 这是针对在任何组合中仅相差一个比特或两个比特的对进行测试的，
 * 无论是(a,b,c)的高位比特组合，还是(a,b,c)的低位比特组合。
 * “差异”被定义为 +, -, ^, 或 ~^。对于 + 和 -，我将输出增量转换为Gray码
 * (a^(a>>1))，这样一串1（通常由减法产生）看起来就像是一个单一的1比特差异。
 * 基本值是伪随机的，除了一位被设置为1外都是零，或者全为零加上一个从零开始的计数器。
 *
 * 对mix()和final()使用单独的函数可以显著提高性能，因为final()不需要
 * 在反向操作中表现良好，但需要影响所有输出比特。
 * 另一方面，mix()不需要影响所有输出比特（影响32比特就足够了）。
 * 原始哈希函数有一个单一的混合操作，必须同时满足这两组要求，因此速度较慢。
 *----------
 */
#define final(a,b,c) \
{ \
  c ^= b; c -= rot(b,14); \
  a ^= c; a -= rot(c,11); \
  b ^= a; b -= rot(a,25); \
  c ^= b; c -= rot(b,16); \
  a ^= c; a -= rot(c, 4); \
  b ^= a; b -= rot(a,14); \
  c ^= b; c -= rot(b,24); \
}

/*
 * hash_bytes() -- 将可变长度的键哈希为32位值
 *		k		: 键（未对齐的可变长度字节数组）
 *		len		: 键的长度，以字节为单位计数
 *
 * 返回一个uint32值。键的每一位都会影响返回值的每一位。
 * 每个1比特和2比特增量都实现了雪崩效应。
 * 约6*len+35条指令。最佳哈希表大小是2的幂。
 * 没必要对素数取模（取模运算速度是如此慢！）。
 * 如果需要少于32比特，请使用位掩码。
 *
 * 该过程绝不能抛出elog(ERROR)；ResourceOwner代码依赖于此不失败。
 *
 * 注意：我们可以轻松地将此函数更改为返回64位哈希值
 * 通过使用b和c的最终值。然而，b的混合效果可能不如c好。
 */
uint32 hash_bytes(const unsigned char *fc_k, int fc_keylen)
{
	uint32		fc_a,
				fc_b,
				fc_c,
				fc_len;

	/* 设置内部状态 */
	fc_len = fc_keylen;
	fc_a = fc_b = fc_c = 0x9e3779b9 + fc_len + 3923095;

	/* 如果源指针是字对齐的，我们使用字宽提取 */
	if (((uintptr_t) fc_k & UINT32_ALIGN_MASK) == 0)
	{
		/* 对齐源数据的代码路径 */
		const uint32 *fc_ka = (const uint32 *) fc_k;

		/* 处理大部分键 */
		while (fc_len >= 12)
		{
			fc_a += fc_ka[0];
			fc_b += fc_ka[1];
			fc_c += fc_ka[2];
			mix(fc_a, fc_b, fc_c);
			fc_ka += 3;
			fc_len -= 12;
		}

		/* 处理最后11个字节 */
		fc_k = (const unsigned char *) fc_ka;
#ifdef WORDS_BIGENDIAN
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 8);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 24);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += fc_ka[1];
				fc_a += fc_ka[0];
				break;
			case 7:
				fc_b += ((uint32) fc_k[6] << 8);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 16);
				/* fall through */
			case 5:
				fc_b += ((uint32) fc_k[4] << 24);
				/* fall through */
			case 4:
				fc_a += fc_ka[0];
				break;
			case 3:
				fc_a += ((uint32) fc_k[2] << 8);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 16);
				/* fall through */
			case 1:
				fc_a += ((uint32) fc_k[0] << 24);
				/* 情况0：没有剩余可添加 */
		}
#else							/* !WORDS_BIGENDIAN */
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 24);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 8);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += fc_ka[1];
				fc_a += fc_ka[0];
				break;
			case 7:
				fc_b += ((uint32) fc_k[6] << 16);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 8);
				/* fall through */
			case 5:
				fc_b += fc_k[4];
				/* fall through */
			case 4:
				fc_a += fc_ka[0];
				break;
			case 3:
				fc_a += ((uint32) fc_k[2] << 16);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 8);
				/* fall through */
			case 1:
				fc_a += fc_k[0];
				/* 情况0：没有剩余可添加 */
		}
#endif							/* WORDS_BIGENDIAN */
	}
	else
	{
		/* 非对齐源数据的代码路径 */

		/* 处理大部分键 */
		while (fc_len >= 12)
		{
#ifdef WORDS_BIGENDIAN
			fc_a += (fc_k[3] + ((uint32) fc_k[2] << 8) + ((uint32) fc_k[1] << 16) + ((uint32) fc_k[0] << 24));
			fc_b += (fc_k[7] + ((uint32) fc_k[6] << 8) + ((uint32) fc_k[5] << 16) + ((uint32) fc_k[4] << 24));
			fc_c += (fc_k[11] + ((uint32) fc_k[10] << 8) + ((uint32) fc_k[9] << 16) + ((uint32) fc_k[8] << 24));
#else							/* !WORDS_BIGENDIAN */
			fc_a += (fc_k[0] + ((uint32) fc_k[1] << 8) + ((uint32) fc_k[2] << 16) + ((uint32) fc_k[3] << 24));
			fc_b += (fc_k[4] + ((uint32) fc_k[5] << 8) + ((uint32) fc_k[6] << 16) + ((uint32) fc_k[7] << 24));
			fc_c += (fc_k[8] + ((uint32) fc_k[9] << 8) + ((uint32) fc_k[10] << 16) + ((uint32) fc_k[11] << 24));
#endif							/* WORDS_BIGENDIAN */
			mix(fc_a, fc_b, fc_c);
			fc_k += 12;
			fc_len -= 12;
		}

		/* 处理最后11个字节 */
#ifdef WORDS_BIGENDIAN
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 8);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 24);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += fc_k[7];
				/* fall through */
			case 7:
				fc_b += ((uint32) fc_k[6] << 8);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 16);
				/* fall through */
			case 5:
				fc_b += ((uint32) fc_k[4] << 24);
				/* fall through */
			case 4:
				fc_a += fc_k[3];
				/* fall through */
			case 3:
				fc_a += ((uint32) fc_k[2] << 8);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 16);
				/* fall through */
			case 1:
				fc_a += ((uint32) fc_k[0] << 24);
				/* 情况0：没有剩余可添加 */
		}
#else							/* !WORDS_BIGENDIAN */
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 24);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 8);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += ((uint32) fc_k[7] << 24);
				/* fall through */
			case 7:
				fc_b += ((uint32) fc_k[6] << 16);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 8);
				/* fall through */
			case 5:
				fc_b += fc_k[4];
				/* fall through */
			case 4:
				fc_a += ((uint32) fc_k[3] << 24);
				/* fall through */
			case 3:
				fc_a += ((uint32) fc_k[2] << 16);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 8);
				/* fall through */
			case 1:
				fc_a += fc_k[0];
				/* 情况0：没有剩余可添加 */
		}
#endif							/* WORDS_BIGENDIAN */
	}

	final(fc_a, fc_b, fc_c);

	/* 设置内部状态 */
	return fc_c;
}

/* 如果种子非零，使用它来扰动内部状态。 */
uint64 hash_bytes_extended(const unsigned char *fc_k, int fc_keylen, uint64 fc_seed)
{
	uint32		fc_a,
				fc_b,
				fc_c,
				fc_len;

	/* 设置内部状态 */
	fc_len = fc_keylen;
	fc_a = fc_b = fc_c = 0x9e3779b9 + fc_len + 3923095;

	/* 如果源指针是字对齐的，我们使用字宽取值 */
	if (fc_seed != 0)
	{
		/* 对齐源数据的代码路径 */
		fc_a += (uint32) (fc_seed >> 32);
		fc_b += (uint32) fc_seed;
		mix(fc_a, fc_b, fc_c);
	}

	/* 如果源指针是字对齐的，我们使用字宽提取 */
	if (((uintptr_t) fc_k & UINT32_ALIGN_MASK) == 0)
	{
		/* 对齐源数据的代码路径 */
		const uint32 *fc_ka = (const uint32 *) fc_k;

		/* 处理大部分键 */
		while (fc_len >= 12)
		{
			fc_a += fc_ka[0];
			fc_b += fc_ka[1];
			fc_c += fc_ka[2];
			mix(fc_a, fc_b, fc_c);
			fc_ka += 3;
			fc_len -= 12;
		}

		/* 处理最后11个字节 */
		fc_k = (const unsigned char *) fc_ka;
#ifdef WORDS_BIGENDIAN
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 8);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 24);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += fc_ka[1];
				fc_a += fc_ka[0];
				break;
			case 7:
				fc_b += ((uint32) fc_k[6] << 8);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 16);
				/* fall through */
			case 5:
				fc_b += ((uint32) fc_k[4] << 24);
				/* fall through */
			case 4:
				fc_a += fc_ka[0];
				break;
			case 3:
				fc_a += ((uint32) fc_k[2] << 8);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 16);
				/* fall through */
			case 1:
				fc_a += ((uint32) fc_k[0] << 24);
				/* 情况0：没有剩余可添加 */
		}
#else							/* !WORDS_BIGENDIAN */
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 24);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 8);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += fc_ka[1];
				fc_a += fc_ka[0];
				break;
			case 7:
				fc_b += ((uint32) fc_k[6] << 16);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 8);
				/* fall through */
			case 5:
				fc_b += fc_k[4];
				/* fall through */
			case 4:
				fc_a += fc_ka[0];
				break;
			case 3:
				fc_a += ((uint32) fc_k[2] << 16);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 8);
				/* fall through */
			case 1:
				fc_a += fc_k[0];
				/* 情况0：没有剩余可添加 */
		}
#endif							/* WORDS_BIGENDIAN */
	}
	else
	{
		/* 非对齐源数据的代码路径 */

		/* 处理大部分键 */
		while (fc_len >= 12)
		{
#ifdef WORDS_BIGENDIAN
			fc_a += (fc_k[3] + ((uint32) fc_k[2] << 8) + ((uint32) fc_k[1] << 16) + ((uint32) fc_k[0] << 24));
			fc_b += (fc_k[7] + ((uint32) fc_k[6] << 8) + ((uint32) fc_k[5] << 16) + ((uint32) fc_k[4] << 24));
			fc_c += (fc_k[11] + ((uint32) fc_k[10] << 8) + ((uint32) fc_k[9] << 16) + ((uint32) fc_k[8] << 24));
#else							/* !WORDS_BIGENDIAN */
			fc_a += (fc_k[0] + ((uint32) fc_k[1] << 8) + ((uint32) fc_k[2] << 16) + ((uint32) fc_k[3] << 24));
			fc_b += (fc_k[4] + ((uint32) fc_k[5] << 8) + ((uint32) fc_k[6] << 16) + ((uint32) fc_k[7] << 24));
			fc_c += (fc_k[8] + ((uint32) fc_k[9] << 8) + ((uint32) fc_k[10] << 16) + ((uint32) fc_k[11] << 24));
#endif							/* WORDS_BIGENDIAN */
			mix(fc_a, fc_b, fc_c);
			fc_k += 12;
			fc_len -= 12;
		}

		/* 处理最后11个字节 */
#ifdef WORDS_BIGENDIAN
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 8);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 24);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += fc_k[7];
				/* fall through */
			case 7:
				fc_b += ((uint32) fc_k[6] << 8);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 16);
				/* fall through */
			case 5:
				fc_b += ((uint32) fc_k[4] << 24);
				/* fall through */
			case 4:
				fc_a += fc_k[3];
				/* fall through */
			case 3:
				fc_a += ((uint32) fc_k[2] << 8);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 16);
				/* fall through */
			case 1:
				fc_a += ((uint32) fc_k[0] << 24);
				/* 情况0：没有剩余可添加 */
		}
#else							/* !WORDS_BIGENDIAN */
		switch (fc_len)
		{
			case 11:
				fc_c += ((uint32) fc_k[10] << 24);
				/* fall through */
			case 10:
				fc_c += ((uint32) fc_k[9] << 16);
				/* fall through */
			case 9:
				fc_c += ((uint32) fc_k[8] << 8);
				/* fall through */
			case 8:
				/* c的最低字节保留用于长度 */
				fc_b += ((uint32) fc_k[7] << 24);
				/* fall through */
			case 7:
				fc_b += ((uint32) fc_k[6] << 16);
				/* fall through */
			case 6:
				fc_b += ((uint32) fc_k[5] << 8);
				/* fall through */
			case 5:
				fc_b += fc_k[4];
				/* fall through */
			case 4:
				fc_a += ((uint32) fc_k[3] << 24);
				/* fall through */
			case 3:
				fc_a += ((uint32) fc_k[2] << 16);
				/* fall through */
			case 2:
				fc_a += ((uint32) fc_k[1] << 8);
				/* fall through */
			case 1:
				fc_a += fc_k[0];
				/* 情况0：没有剩余可添加 */
		}
#endif							/* WORDS_BIGENDIAN */
	}

	final(fc_a, fc_b, fc_c);

	/* 设置内部状态 */
	return ((uint64) fc_b << 32) | fc_c;
}

/*
 * hash_bytes_uint32_extended() -- 将32位值哈希到64位值，带种子
 *
 * 类似于hash_bytes_uint32，这是一个方便函数。
 */
uint32 hash_bytes_uint32(uint32 fc_k)
{
	uint32		fc_a,
				fc_b,
				fc_c;

	fc_a = fc_b = fc_c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
	fc_a += fc_k;

	final(fc_a, fc_b, fc_c);

	/* 设置内部状态 */
	return fc_c;
}

/*
 * string_hash: 针对以NUL结尾字符串的哈希函数。
 *
 * 注意：如果未指定其他哈希函数，则这是默认哈希函数。
 */
uint64 hash_bytes_uint32_extended(uint32 fc_k, uint64 fc_seed)
{
	uint32		fc_a,
				fc_b,
				fc_c;

	fc_a = fc_b = fc_c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;

	if (fc_seed != 0)
	{
		fc_a += (uint32) (fc_seed >> 32);
		fc_b += (uint32) fc_seed;
		mix(fc_a, fc_b, fc_c);
	}

	fc_a += fc_k;

	final(fc_a, fc_b, fc_c);

	/* 设置内部状态 */
	return ((uint64) fc_b << 32) | fc_c;
}

/*
 * tag_hash: 针对固定大小标签值的哈希函数
 */
uint32 string_hash(const void *fc_key, Size fc_keysize)
{
	/*
 * uint32_hash: 针对uint32或int32的哈希函数
 *
 * （tag_hash也适用于这种情况，但速度较慢）
 */
	Size		fc_s_len = strlen((const char *) fc_key);

	fc_s_len = Min(fc_s_len, fc_keysize - 1);
	return hash_bytes((const unsigned char *) fc_key, (int) fc_s_len);
}

//burtleburtle.net/bob/hash/doobs.html,
uint32 tag_hash(const void *fc_key, Size fc_keysize)
{
	return hash_bytes((const unsigned char *) fc_key, (int) fc_keysize);
}

/*
 * uint32_hash: hash function for keys that are uint32 or int32
 *
 * (tag_hash works for this case too, but is slower)
 */
uint32 uint32_hash(const void *fc_key, Size fc_keysize)
{
	Assert(fc_keysize == sizeof(uint32));
	return hash_bytes_uint32(*((const uint32 *) fc_key));
}
